package sort

import "fmt"

func SortArray(nums []int) []int {
	insertSort(nums)
	return nums
}

// 快排
func mergeSort(nums []int, left int, right int) {
	if left >= right {
		return
	}
	var mid int = (right + left) / 2
	mergeSort(nums, left, mid)
	mergeSort(nums, mid+1, right)
	merge(nums, left, mid, right)
}

func merge(nums []int, left int, mid int, right int) {
	var tmp []int
	l, r := left, mid+1
	for l <= mid || r <= right {
		if l > mid {
			tmp = append(tmp, nums[r])
			r++
		} else if r > right {
			tmp = append(tmp, nums[l])
			l++
		} else if nums[l] > nums[r] {
			tmp = append(tmp, nums[r])
			r++
		} else {
			tmp = append(tmp, nums[l])
			l++
		}
	}

	for i := 0; i < len(tmp); i++ {
		nums[i+left] = tmp[i]
	}

}

// 冒泡排序法
func bubbleSort(nums []int) {
	l := len(nums)
	for i := 0; i < l; i++ {
		for j := 0; j < l-i-1; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}

// 选择排序法
func selectSort(nums []int) {
	l := len(nums)
	for i := 0; i < l; i++ {
		idx := i
		for j := i; j < l; j++ {
			if nums[j] < nums[idx] {
				idx = j
			}
		}
		if i != idx {
			nums[i], nums[idx] = nums[idx], nums[i]
		}
	}
}

// 插入排序
func insertSort(nums []int) {
	for i := 0; i < len(nums); i++ {
		temp := nums[i]
		j := i
		for ; j > 0; j-- {
			if nums[j-1] > temp {
				nums[j] = nums[j-1]
			} else {
				break
			}
		}
		nums[j] = temp
	}
}
func insertSort2(nums []int) {
	for i := 0; i < len(nums); i++ {
		temp := nums[i]
		j := i - 1
		for ; j >= 0; j-- {
			if nums[j] > temp {
				nums[j+1] = nums[j]
			} else {
				break
			}
		}
		nums[j+1] = temp
	}
}

// 希尔排序
func shellSort(nums []int, gap int) {
	for ; gap > 0; gap /= 2 {
		shell(nums, gap)
	}
}
func shell(nums []int, gap int) {
	for i := 0; i < len(nums); i += gap {
		temp := nums[i]
		j := i - gap
		for ; j >= 0; j -= gap {
			if nums[j] > temp {
				nums[j+gap] = nums[j]
			} else {
				break
			}
		}
		nums[j+gap] = temp
	}
}

// 快排
func quickSort(nums []int) {
	quick(nums, 0, len(nums)-1)
}

func quick(nums []int, start, end int) {
	if start >= end {
		return
	}
	pivot := partition(nums, start, end)
	quick(nums, pivot+1, end)
	quick(nums, start, pivot-1)
}

func partition(nums []int, left, right int) int {
	n := left
	// 初始基准
	pivot := nums[n]
	for left < right {
		for left < right && nums[right] >= pivot {
			right--
		}
		for left < right && nums[left] <= pivot {
			left++
		}
		fmt.Printf("nums[left]: %v,nums[right]: %v,\n", nums[left], nums[right])
		nums[left], nums[right] = nums[right], nums[left]
	}
	nums[n], nums[left] = nums[left], nums[n]
	fmt.Printf("nums: %v\n", nums)
	return left
}

// 堆排

func build_heap(nums []int, n int) {
	var last_node int = n - 1
	var parent int = (last_node - 1) / 2
	for i := parent; i >= 0; i-- {
		heapify_for(nums, n, parent)
	}

}

func heapify_for(nums []int, n, parent int) {
	var temp int = nums[parent]
	for i := parent*2 + 1; i < n; i = i*2 + 1 {
		c1, c2 := i, i+1
		if i < n-1 && nums[c1] < nums[c2] {
			i++
		}
		if temp > nums[i] {
			break
		}
		nums[parent] = nums[i]
		parent = i
	}
	nums[parent] = temp
}

func heapSort(nums []int, n int) {
	build_heap(nums, n)
	for i := n - 1; i >= 0; i-- {
		nums[i], nums[0] = nums[0], nums[i]
		heapify_for(nums, i, 0)
	}
}

// 桶排
